/*
 * Created on Thu Dec 01 2022
 *
 * leetcode 22: 括号生成，https://leetcode.cn/problems/generate-parentheses/
 */


#include<vector>
#include<iostream>

using namespace std;

class Solution {
public:

    // bool valid(string str){
    //     auto pos = str.find("()");
    //     while(string::npos != pos){
    //         str.replace(pos, 2, "");
    //         pos = str.find("()");
    //     }
    //     return str.size() == 0 ? true : false;
    // }
    // vector<string> ret;

    // vector<string> generateParenthesis(int n) {
    //     // string options(n, '(');
    //     // options.append(n, ')');

    //     dfs(2*n, "");
    //     vector<string> ret1;
    //     for(string s : ret){
    //         if(valid(s)){
    //             ret1.push_back(s);
    //         }
    //     }
    //     return ret1;
    // }

    // void dfs(int level, string str){
        
    //     if(level == 0){
    //         ret.push_back(str);
    //         return;
    //     }
    //     dfs(level - 1, str.append("("));

    //     str.clear();
    //     level = 4;

    //     dfs(level - 1, str.append(")"));
    // }

    
    vector<string> generateParenthesis(int n) {
        vector<string> ret;
        string str;
        backtrack(ret, 0, 0, n, str);
        return ret;
    }

    // left, right: 左、右括号的数量
    // n: n对括号
    // str: 保存中间结果
    // ret: 保存最终结果
    void backtrack(vector<string>& ret, int left, int right, int n, string& str)
    {
        if(str.size() == 2*n){
            ret.push_back(str);
            return;
        }
        if(left < n){
            str.append("(");
            backtrack(ret, left + 1, right, n, str);
            str.pop_back();
        }
        if(right < left){
            str.append(")");
            backtrack(ret, left, right + 1, n, str);
            str.pop_back();
        }

    }

    void print(vector<string> v){
        for(string s : v){
            cout<<s<<",";
        }
        cout<<endl;
    }
   
};

void test_01(){
    Solution slu;
    vector<string> ret = slu.generateParenthesis(5);
    assert(ret.size() == 42);
    slu.print(ret);
}

void test_02(){
    Solution slu;
    vector<string> ret = slu.generateParenthesis(3);
    assert(ret.size() == 5);
    slu.print(ret);
}

int main(){

    test_01();
    test_02();

    return 0;
}